競プロ典型 90 問 003
(工事中)
解き方
解答例
下は上記の方法で解いたときの提出結果である。また、その提出の際に提出したソースコードをその下に転記する。
code: C
typedef struct list {
int op;
struct list* next;
} list;
void func(int v, list **e, int l, int *l_max, int *farthest, int *visited) {
int tmp_ans = l;
return;
}
if (tmp_ans > *l_max) {
*l_max = tmp_ans;
*farthest = v;
}
while (lst != NULL) {
func(lst->op, e, l+1, l_max, farthest, visited);
lst = lst->next;
}
return;
}
int main () {
int n = 0;
int res = 0;
int v = 1;
int ans = 0;
res = scanf("%d", &n);
for (int i = 0; i < n-1; i++) {
int a = 0;
int b = 0;
list *e_a = NULL;
list *e_b = NULL;
res = scanf("%d", &a);
res = scanf("%d", &b);
e_a = (list *)malloc(sizeof(list));
e_b = (list *)malloc(sizeof(list));
if (e_a == NULL || e_b == NULL) {
exit(0);
}
e_a->op = b;
e_b->op = a;
}
func(v, e, 0, &ans, &v, visited);
func(v, e, 0, &ans, &v, visited);
printf("%d\n", ans+1);
return 0;
}
私の提出一覧
table: submissions_atcoder_typical90_003
提出のURL 提出時刻 結果 備考
感想
ローカルにおいてあったzakkan.txt（雑感）に書かれていたこと
雑感には、木であることはすぐにわかると書いているが、競技プログラミングにまだそこまで慣れていない時期に、この事実はどこで知ったのだろうか。
直径という概念はまだ知らなかったけれど、検索したら出てきたので解けたのは、なんとなく覚えがある
003 - Longest Circular Road（★4）
日時: 2021-05-03 15:48:02
都市に個数より道路の本数が1少なく、どの都市間も行き来できるという設定から
都市の接続関係は（グラフ理論における）木であることはすぐにわかる。
そのため、この問題は下の問題に言い換えられる（木の直径と言うらしい）
「木が与えられたときに、そのなかで最も長いpath の長さを求める」
検索するとこの問題は下のように、ある頂点から最も遠い頂点を求める処理を
2回行えば解けるという情報を見つけて、そのとおりに解いたと思われる。
「適当な頂点から最も遠い頂点を求め、そこから最も遠い頂点を求める」
改めて提出を確認すると、main 関数内で宣言した配列の型が誤っており、
このときは動作に影響はなかったが、コンパイルエラーが出ていた。
提出したものをそのまま集めているため、ここに置いてあるソースも誤ったままである。
最近はコンパイルエラーが出ていないか確認するようにしている